package zuo.algo.c04;

import zuo.algo.util.SortUtils;

import java.util.Arrays;

/**
 * 00:08-堆和堆排序
 */
public class HeapSort {

    public static void sort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            upAdjust(arr, i);
        }

        for (int i = arr.length - 1; i > 0; i--) {
            SortUtils.swap(arr, 0, i);
            downAdjust(arr, i - 1);
        }
    }

    public static void sort1(int[] arr) {
        for (int i = arr.length - 1; i >= 0; i--) {
            downAdjust(arr, i, arr.length - 1);
        }

        for (int i = arr.length - 1; i > 0; i--) {
            SortUtils.swap(arr, 0, i);
            downAdjust(arr, i - 1);
        }
    }

    public static void upAdjust(int[] arr, int idx) {
        while (idx > 0) {
            int pIdx = (idx - 1) / 2;
            if (arr[idx] > arr[pIdx]) {
                SortUtils.swap(arr, idx, pIdx);
            }
            idx = pIdx;
        }
    }

    public static void downAdjust(int[] arr, int start, int end) {
        int idx = start;
        while (idx < end) {
            int cIdx = 2 * idx + 1;
            if (cIdx > end) {
                break;
            }
            cIdx = cIdx + 1 > end || arr[cIdx] >= arr[cIdx+1] ? cIdx : cIdx + 1;
            if (arr[cIdx] > arr[idx]) {
                SortUtils.swap(arr, idx, cIdx);
            }
            idx = cIdx;
        }
    }

    public static void downAdjust(int[] arr, int end) {
        int idx = 0;
        while (idx < end) {
            int cIdx = 2 * idx + 1;
            if (cIdx > end) {
                break;
            }
            int temp = cIdx + 1 > end || arr[cIdx] >= arr[cIdx + 1] ? arr[cIdx] : arr[++cIdx];
            if (arr[idx] < temp) {
                SortUtils.swap(arr, idx, cIdx);
            }
            idx = cIdx;
        }
    }

    public static void main(String[] args) {
        int maxLen = 100000;
        for (int i = 0; i < 100000; i++) {
            int[] arr1 = SortUtils.getRandomArr(maxLen);
            int[] arr2 = Arrays.copyOf(arr1, arr1.length);
            int[] arr3 = Arrays.copyOf(arr1, arr1.length);
            sort(arr1);
            Arrays.sort(arr2);
            sort1(arr3);
            SortUtils.assertArr(arr1, arr2);
            SortUtils.assertArr(arr1, arr3);
            System.out.println(i);
        }
    }
}
